package me.eg.third;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 47. 全排列 II
 *
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 * https://leetcode-cn.com/problems/permutations-ii/
 */
public class PermuteUnique {
    private int[] nums;
    private int n;
    private List<List<Integer>> res;
    private List<Integer> al;
    private boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums); // 先排序，后面排除重复的剪枝依赖有序

        this.nums = nums;
        this.n = nums.length;
        res = new ArrayList<>();
        al = new ArrayList<>();
        used = new boolean[n];
        recursion();
        return res;
    }

    private void recursion(){
        if(al.size() == n) {
            res.add(new ArrayList(al));
            return;
        }

        int last = 11; // 初始化，num的范围是[-10,10]
        for (int i = 0; i < n; i++) {
            if (nums[i] == last) continue; // 这次分支和上次分支一样，已计算，跳过
            if(used[i]) continue;
            al.add(nums[i]);
            used[i] = true;
            recursion();
            used[i] = false;
            last = al.get(al.size() - 1); //记录上次计算的分支
            al.remove(al.size() - 1);
        }
    }
}
